package j20251109;

import java.util.ArrayList;
import java.util.List;

public class Solution2 {
    int m,n;
    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
    public List<List<Integer>> pacificAtlantic(int[][] h) {
        m=h.length;
        n=h[0].length;
        boolean[][] pac=new boolean[m][n];
        boolean[][] atl=new boolean[m][n];
        for(int i=0;i<m;i++){
            dfs(h,i,0,pac);
            dfs(h,i,n-1,atl);
        }
        for(int j=0;j<n;j++){
            dfs(h,0,j,pac);
            dfs(h,m-1,j,atl);
        }
        List<List<Integer>> ret=new ArrayList<>();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(pac[i][j]&&atl[i][j]){
                    List<Integer> tmp=new ArrayList<>();
                    tmp.add(i);
                    tmp.add(j);
                    ret.add(tmp);
                }
            }
        }
        return ret;
    }
    public void dfs(int[][] h,int i,int j,boolean[][] vis){
        vis[i][j]=true;
        for(int k=0;k<4;k++){
            int x=i+dx[k],y=j+dy[k];
            if(x>=0&&x<m&&y>=0&&y<n&&!vis[x][y]&&h[x][y]>=h[i][j]){
                dfs(h,x,y,vis);
            }
        }
    }
}
